﻿/**
 * Copyright (C) 2012 original author and authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.Concurrent;
using System.Threading;
using System.Reflection;
using System.Runtime.Serialization;

namespace NGuice.Inject.Internal.Util
{
    /// <summary>
    /// 此类从java并发Map移植而来
    /// </summary>
    /// <typeparam name="K"></typeparam>
    /// <typeparam name="V"></typeparam>
    public interface ConcurrentMap<K, V> : IDictionary<K, V>
    {
        /**
         * If the specified key is not already associated
         * with a value, associate it with the given value.
         * This is equivalent to
         * <pre>
         *   if (!map.containsKey(key))
         *       return map.put(key, value);
         *   else
         *       return map.get(key);</pre>
         * except that the action is performed atomically.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with the specified key, or
         *         <tt>null</tt> if there was no mapping for the key.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with the key,
         *         if the implementation supports null values.)
         * @throws UnsupportedOperationException if the <tt>put</tt> operation
         *         is not supported by this map
         * @throws ClassCastException if the class of the specified key or value
         *         prevents it from being stored in this map
         * @throws NullPointerException if the specified key or value is null,
         *         and this map does not permit null keys or values
         * @throws IllegalArgumentException if some property of the specified key
         *         or value prevents it from being stored in this map
         *
         */
        V PutIfAbsent(K key, V value);

        /**
         * Removes the entry for a key only if currently mapped to a given value.
         * This is equivalent to
         * <pre>
         *   if (map.containsKey(key) &amp;&amp; map.get(key).equals(value)) {
         *       map.remove(key);
         *       return true;
         *   } else return false;</pre>
         * except that the action is performed atomically.
         *
         * @param key key with which the specified value is associated
         * @param value value expected to be associated with the specified key
         * @return <tt>true</tt> if the value was removed
         * @throws UnsupportedOperationException if the <tt>remove</tt> operation
         *         is not supported by this map
         * @throws ClassCastException if the key or value is of an inappropriate
         *         type for this map
         *         (<a href="../Collection.html#optional-restrictions">optional</a>)
         * @throws NullPointerException if the specified key or value is null,
         *         and this map does not permit null keys or values
         *         (<a href="../Collection.html#optional-restrictions">optional</a>)
         */
        bool Remove(K key, V value);

        /**
         * Replaces the entry for a key only if currently mapped to a given value.
         * This is equivalent to
         * <pre>
         *   if (map.containsKey(key) &amp;&amp; map.get(key).equals(oldValue)) {
         *       map.put(key, newValue);
         *       return true;
         *   } else return false;</pre>
         * except that the action is performed atomically.
         *
         * @param key key with which the specified value is associated
         * @param oldValue value expected to be associated with the specified key
         * @param newValue value to be associated with the specified key
         * @return <tt>true</tt> if the value was replaced
         * @throws UnsupportedOperationException if the <tt>put</tt> operation
         *         is not supported by this map
         * @throws ClassCastException if the class of a specified key or value
         *         prevents it from being stored in this map
         * @throws NullPointerException if a specified key or value is null,
         *         and this map does not permit null keys or values
         * @throws IllegalArgumentException if some property of a specified key
         *         or value prevents it from being stored in this map
         */
        bool Replace(K key, V oldValue, V newValue);

        /**
         * Replaces the entry for a key only if currently mapped to some value.
         * This is equivalent to
         * <pre>
         *   if (map.containsKey(key)) {
         *       return map.put(key, value);
         *   } else return null;</pre>
         * except that the action is performed atomically.
         *
         * @param key key with which the specified value is associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with the specified key, or
         *         <tt>null</tt> if there was no mapping for the key.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with the key,
         *         if the implementation supports null values.)
         * @throws UnsupportedOperationException if the <tt>put</tt> operation
         *         is not supported by this map
         * @throws ClassCastException if the class of the specified key or value
         *         prevents it from being stored in this map
         * @throws NullPointerException if the specified key or value is null,
         *         and this map does not permit null keys or values
         * @throws IllegalArgumentException if some property of the specified key
         *         or value prevents it from being stored in this map
         */
        V Replace(K key, V value);
    }

    /// <summary>
    /// 并发字典实现的一个框架类。本身不能被扩展并不包含任何方法。他使用<code>Builder</code>
    /// 类创建并发字典实例。客户端库实现<code>Strategy</code>,且次类提供实现ConcurrentDictionary
    /// 的并发数据结构。另外，获取方法会在后台原子的计算值（<code>Builder.BuildComputingMap(ComputingStrategy, 
    /// com.google.inject.internal.util.Function)</code>).结果哈希表支持完整的并发获取和可调整的并发更新。即使
    /// 所有操作都是线程安全的，获取操作并不意味着锁定。
    /// 以下策略模拟并发字典的行为：
    /// <code>
    /// class ConcurrentHashMapStrategy<K, V>：CustomConcurrentHashMap.Strategy<K, V, InternalEntry<K, V>>, Serializable {
    ///     public InternalEntry<K, V> NewEntry(K key, int hash, InternalEntry<K, V> next) {
    ///         return new InternalEntry<K, V>(key, hash, null, next);
    ///     }
    ///     public InternalEntry<K, V> CopyEntry(K key, InternalEntry<K, V> original, InternalEntry<K, V> next) {
    ///         return new InternalEntry<K, V>(key, original.hash, original.value, next);
    ///     }
    ///     public void setValue(InternalEntry<K, V> entry, V value) {
    ///         entry.value = value;
    ///     }
    ///     public V getValue(InternalEntry<K, V> entry) { return entry.value; }
    ///     public boolean equalKeys(K a, Object b) { return a.equals(b); }
    ///     public boolean equalValues(V a, Object b) { return a.equals(b); }
    ///     public int hashKey(Object key) { return key.hashCode(); }
    ///     public K getKey(InternalEntry<K, V> entry) { return entry.key; }
    ///     public InternalEntry<K, V> getNext(InternalEntry<K, V> entry) {
    ///         return entry.next;
    ///     }
    ///     public int getHash(InternalEntry<K, V> entry) { return entry.hash; }
    ///     public void setInternals(CustomConcurrentHashMap.Internals<K, V,
    ///         InternalEntry<K, V>> internals) {} // ignored
    ///     }
    ///     
    ///     class InternalEntry<K, V> {
    ///         readonly K key;
    ///         readonly int hash;
    ///         volatile V value;
    ///         final InternalEntry<K, V> next;
    ///         InternalEntry(K key, int hash, V value, InternalEntry<K, V> next) {
    ///             this.key = key;
    ///             this.hash = hash;
    ///             this.value = value;
    ///             this.next = next;
    ///         }
    ///     }
    ///  }
    /// </code>
    /// 使用Strategy创建并发字典如下：
    /// <code>
    /// ConcurrentDictionary<K, V> map = new CustomConcurrentHashMap.Builder().build(new ConcurrentHashMapStrategy<K, V>());
    /// </code>
    /// </summary>
    public sealed class CustomConcurrentDictionary
    {

        private CustomConcurrentDictionary() { }

        /// <summary>
        /// 构建自定义的并发字典
        /// </summary>
        public sealed class Builder
        {

            internal float loadFactor = 0.75f;
            internal int initialCapacity = 16;
            internal int concurrencyLevel = 16;

            /// <summary>
            /// 设置加载因子，默认0.75
            /// </summary>
            /// <param name="loadFactor"></param>
            /// <returns></returns>
            public Builder LoadFactor(float loadFactor)
            {
                if (loadFactor <= 0)
                {
                    throw new ArgumentException();
                }
                this.loadFactor = loadFactor;
                return this;
            }


            public Builder InitialCapacity(int initialCapacity)
            {
                if (initialCapacity < 0)
                {
                    throw new ArgumentException();
                }
                this.initialCapacity = initialCapacity;
                return this;
            }

            /// <summary>
            /// </summary>
            /// <param name="concurrencyLevel"></param>
            /// <returns></returns>
            public Builder ConcurrencyLevel(int concurrencyLevel)
            {
                if (concurrencyLevel <= 0)
                {
                    throw new ArgumentException();
                }
                this.concurrencyLevel = concurrencyLevel;
                return this;
            }

            /// <summary>
            /// 使用给定的策略创建一个新的并发字典
            /// </summary>
            /// <typeparam name="K">并发字典key类型</typeparam>
            /// <typeparam name="V">并发字典value类型</typeparam>
            /// <typeparam name="E">并发字典内部的entry类型</typeparam>
            /// <param name="strategy"></param>
            /// <returns></returns>
            /// <exception cref="NullReferenceException">策略为null则抛出此异常</exception>
            public ConcurrentMap<K, V> BuildDictionary<K, V, E>(Strategy<K, V, E> strategy)
                //where V : class
                where E : class
            {
                if (strategy == null)
                {
                    throw new NullReferenceException("strategy");
                }
                return new Impl<K, V, E>(strategy, this);
            }

            /// <summary>
            /// 根据一个给定策略创建一个并发字典，次策略支持原子的，后台的计算值。并发
            /// 字典获取值的方法将自动使用传入的computer计算，或者如有必要将等待另一个
            /// 线程计算。如果实体的值没有计算完成，除Get方法外的其他查询方法将立即返回。
            /// </summary>
            /// <typeparam name="K">并发字典key类型</typeparam>
            /// <typeparam name="V">并发字典value类型</typeparam>
            /// <typeparam name="E">并发字典内部的entry类型</typeparam>
            /// <param name="strategy"></param>
            /// <param name="computer"></param>
            /// <returns></returns>
            public ConcurrentMap<K, V> BuildComputingDictionary<K, V, E>(ComputingStrategy<K, V, E> strategy, Func<K, V> computer)
                //where V:class
                where E:class
            {
                if (strategy == null)
                {
                    throw new NullReferenceException("strategy");
                }
                if (computer == null)
                {
                    throw new NullReferenceException("computer");
                }

                return new ComputingImpl<K, V, E>(strategy, this, computer);
            }
        }

        /// <summary>
        /// 针对客户的并发哈希字典的实现的行为。被框架应用于创建新实体并在其上执行操作。
        /// 方法参数除非特殊要求，永远不要使用null。CustomConcurrentDictionary不允许null
        /// 作为key，通常也不允许使用null作为value，但实体可以基于特殊理由具有null 
        /// key或null值。例如，key或value可能已经被垃圾回收。这意味着，此类对待具有
        /// null key和value为部分回收且大部分时间将忽略。实体将进入一个部分回收状态。策略
        /// 实现将主动删除部分回收实体以便相关方法（如Count等）返回最新结果
        /// </summary>
        /// <typeparam name="K">在返回的字典中的key类型</typeparam>
        /// <typeparam name="V">在返回的字典中的value类型</typeparam>
        /// <typeparam name="E">内部实体类型，不直接暴露给客户</typeparam>
        public interface Strategy<K, V, E>
            //where V : class
            where E : class
        {
            /// <summary>
            /// 为给定的key和给定的下一个实体构造一个新的实体。此方法根据下一个
            /// 实体是否为null返回不同的值。例如，如果下一个为null，此工厂将使用
            /// 一个实体类而不在没必要的域上浪费内存
            /// </summary>
            /// <param name="key">实体的key</param>
            /// <param name="hash">被HashKey返回的哈希值</param>
            /// <param name="next">下一个实体，用于当实现一个链表哈希时使用</param>
            /// <returns></returns>
            E NewEntry(K key, int hash, E next);

            /// <summary>
            /// CustomConcurrentDictionary使用此方法删除其他实体或扩展内部表格
            /// </summary>
            /// <param name="key"></param>
            /// <param name="original"></param>
            /// <param name="newNext"></param>
            /// <returns></returns>
            E CopyEntry(K key, E original, E newNext);

            /// <summary>
            /// 使用volatile语义设置一个实体的值
            /// </summary>
            /// <param name="entry"></param>
            /// <param name="value"></param>
            void SetValue(E entry, V value);

            V GetValue(E entry);

            bool EqualKeys(K a, object b);

            bool EqualValues(V a, object b);

            /// <summary>
            /// 获取给定key的哈希码
            /// </summary>
            /// <param name="key"></param>
            /// <returns></returns>
            int HashKey(object key);

            /// <summary>
            /// 获取给定实体的key，如果实体被垃圾回收，可能返回null
            /// </summary>
            /// <param name="entry"></param>
            /// <returns></returns>
            K GetKey(E entry);

            E GetNext(E entry);

            /// <summary>
            /// 当创建给定实体时传递给NewEntry的哈希码
            /// </summary>
            /// <param name="entry"></param>
            /// <returns></returns>
            int GetHash(E entry);

            /// <summary>
            /// 提供一个API用于与哈希字典的内部实体进行直接的交互。当字典被创建后调用一次。
            /// 如果无需与内部实体交互的策略，可以简单忽略参数
            /// </summary>
            /// <param name="internals"></param>
            void SetInternals(Internals<K, V, E> internals);
        }

        /// <summary>
        /// 用于访问字典的内部实体
        /// </summary>
        /// <typeparam name="K"></typeparam>
        /// <typeparam name="V"></typeparam>
        /// <typeparam name="E"></typeparam>
        public interface Internals<K, V, E>
        {
            /// <summary>
            /// 获取对应给定key的内部实体
            /// Returns the internal entry corresponding to the given key from the map.
            /// </summary>
            /// <param name="key"></param>
            /// <returns></returns>
            /// <exception cref="NullReferenceException">key为null</exception>
            E GetEntry(K key);

            /// <summary>
            /// 如果实体value匹配给定值则从字典中删除给定实体
            /// </summary>
            /// <param name="entry"></param>
            /// <param name="value"></param>
            /// <returns></returns>
            /// <exception cref="NullReferenceException">实体为null</exception>
            bool RemoveEntry(E entry, V value);

            bool RemoveEntry(E entry);
        }

        /// <summary>
        /// 策略对象的扩展接口用于添加在demand后台中计算值的支持。实现应该典型的
        /// 在NewEntry方法中初始化实体值为一个占位符值以便WaitForValue能够告知在
        /// pre-intialized值与in-progress计算之间的不同。CopyEntry必须检测并处理
        /// 当一个实体在计算期间拷贝的情况。如果希望阻止用户直接设置值，则可以在
        /// SetValue中抛出UnsupportedOperationException异常
        /// </summary>
        /// <typeparam name="K"></typeparam>
        /// <typeparam name="V"></typeparam>
        /// <typeparam name="E"></typeparam>
        public interface ComputingStrategy<K, V, E> : Strategy<K, V, E>
            where E:class
        {
            /// <summary>
            /// 为给定的key计算值并存储在给定的实体中，作为字典Get的结果。如果此方法
            /// 抛出异常，则CustomConcurrentDictionary将删除实体并在下一次请求中重新计算
            /// </summary>
            /// <param name="key"></param>
            /// <param name="entry"></param>
            /// <param name="computer"></param>
            /// <returns></returns>
            /// <exception cref="ComputationException">计算抛出的异常</exception>
            /// <exception cref="NullReferenceException">如果计算器返回null</exception>
            V Compute(K key, E entry, Func<K, V> computer);

            /// <summary>
            /// 从实体中获取值，这个值如有必要将被Compute计算并设置。如果值
            /// 不是有效的，则将返回null
            /// </summary>
            /// <param name="entry"></param>
            /// <returns></returns>
            /// <exception cref="ThreadInterruptedException">在等待期间计算线程终止</exception>
            V WaitForValue(E entry);
        }


        private static int Rehash(int h)
        {
            // Spread bits to regularize both segment and index locations,
            // using variant of single-word Wang/Jenkins hash.
            h += (int)((h << 15) ^ 0xffffcd7d);
            h ^= Hashing.RightMove(h, 10);
            h += (h << 3);
            h ^= Hashing.RightMove(h, 6);
            h += (h << 2) + (h << 14);
            return h ^ Hashing.RightMove(h, 16);
        }

        /// <summary>
        /// 并发字典实现
        /// </summary>
        /// <typeparam name="K"></typeparam>
        /// <typeparam name="V"></typeparam>
        /// <typeparam name="E"></typeparam>
        [Serializable]
        public class Impl<K, V, E> : ConcurrentMap<K, V>, ISerializable
            where E : class
            //where V : class
        {

            /* ---------------- Constants -------------- */

            /// <summary>
            /// 最大容量。用于最大值被构造函数的参数隐式指定
            /// </summary>
             const int MAXIMUM_CAPACITY = 1 << 30;

            /// <summary>
            /// 允许segments的最大数
            /// </summary>
             const int MAX_SEGMENTS = 1 << 16; // slightly conservative

            /// <summary>
            /// 同步锁定的实体数
            /// </summary>
             const int RETRIES_BEFORE_LOCK = 2;

            /* ---------------- Fields -------------- */

            public readonly Strategy<K, V, E> strategy;

            /// <summary>
            /// segment的索引的阉值。key哈希码的高位字节被用于选择segment
            /// </summary>
            public readonly int segmentMask;

            /// <summary>
            /// 在segment中索引的shift切换值。他用于在相同bucket结束和相同segment结束之间阻止实体
            /// </summary>
            public readonly int segmentShift;

            /// <summary>
            /// 每一个segment都是一个特定的哈希表
            /// </summary>
            public readonly Segment[] segments;

            /// <summary>
            /// 哈希表的加载因子
            /// </summary>
            public readonly float loadFactor;

            /// <summary>
            /// 反序列化，参考GetObjectData（initialCapacity、loadFactor、concurrencyLevel、strategy、
            /// key0.key1....、key.tostring、null）
            /// </summary>
            /// <param name="info"></param>
            /// <param name="ctxt"></param>
            public Impl(SerializationInfo info, StreamingContext ctxt)
            {
                int initialCapacity = info.GetInt32("initialCapacity");
                float loadFactor = (float)info.GetDouble("loadFactor");
                int concurrencyLevel = info.GetInt32("concurrencyLevel");
                Strategy<K, V, E> strategy = (Strategy<K, V, E>)info.GetValue("strategy", typeof(Strategy<K, V, E>));

                Fields.loadFactor.SetValue(this, loadFactor);

                if (concurrencyLevel > MAX_SEGMENTS)
                {
                    concurrencyLevel = MAX_SEGMENTS;
                }

                // Find power-of-two sizes best matching arguments
                int segmentShift = 0;
                int segmentCount = 1;
                while (segmentCount < concurrencyLevel)
                {
                    ++segmentShift;
                    segmentCount <<= 1;
                }
                Fields.segmentShift.SetValue(this, 32 - segmentShift);
                Fields.segmentMask.SetValue(this, segmentCount - 1);
                Fields.segments.SetValue(this, NewSegmentArray(segmentCount));

                if (initialCapacity > MAXIMUM_CAPACITY)
                {
                    initialCapacity = MAXIMUM_CAPACITY;
                }

                int segmentCapacity = initialCapacity / segmentCount;
                if (segmentCapacity * segmentCount < initialCapacity)
                {
                    ++segmentCapacity;
                }

                int segmentSize = 1;
                while (segmentSize < segmentCapacity)
                {
                    segmentSize <<= 1;
                }
                for (int i = 0; i < this.segments.Length; ++i)
                {
                    this.segments[i] = new Segment(segmentSize, this);
                }

                Fields.strategy.SetValue(this, strategy);

                for (int i = 0; i < initialCapacity; i++)
                {
                    K key = (K)info.GetValue("key" + i, typeof(K));
                    if (key == null)
                    {
                        break; // terminator
                    }
                    V value = (V)info.GetValue(key.ToString(), typeof(V));
                    Add(key, value);
                }
            }

            /// <summary>
            /// 创建一个新的、空的具有特定策略的字典，初始化容量、加载因子和并发级别
            /// </summary>
            /// <param name="strategy"></param>
            /// <param name="builder"></param>
            public Impl(Strategy<K, V, E> strategy, Builder builder)
            {
                this.loadFactor = builder.loadFactor;
                int concurrencyLevel = builder.concurrencyLevel;
                int initialCapacity = builder.initialCapacity;

                if (concurrencyLevel > MAX_SEGMENTS)
                {
                    concurrencyLevel = MAX_SEGMENTS;
                }

                // Find power-of-two sizes best matching arguments
                int segmentShift = 0;
                int segmentCount = 1;
                while (segmentCount < concurrencyLevel)
                {
                    ++segmentShift;
                    segmentCount <<= 1;
                }
                this.segmentShift = 32 - segmentShift;
                segmentMask = segmentCount - 1;
                this.segments = NewSegmentArray(segmentCount);

                if (initialCapacity > MAXIMUM_CAPACITY)
                {
                    initialCapacity = MAXIMUM_CAPACITY;
                }

                int segmentCapacity = initialCapacity / segmentCount;
                if (segmentCapacity * segmentCount < initialCapacity)
                {
                    ++segmentCapacity;
                }

                int segmentSize = 1;
                while (segmentSize < segmentCapacity)
                {
                    segmentSize <<= 1;
                }
                for (int i = 0; i < this.segments.Length; ++i)
                {
                    this.segments[i] = new Segment(segmentSize, this);
                }

                this.strategy = strategy;

                strategy.SetInternals(new InternalsImpl(this));
            }

            internal int Hash(object key)
            {
                int h = strategy.HashKey(key);
                return Rehash(h);
            }

            [Serializable]
            public class InternalsImpl : Internals<K, V, E>
            {
                internal Impl<K, V, E> impl;

                public InternalsImpl(Impl<K, V, E> impl)
                {
                    this.impl = impl;
                }

                public E GetEntry(K key)
                {
                    if (key == null)
                    {
                        throw new NullReferenceException("key");
                    }
                    int hash = impl.Hash(key);
                    return impl.SegmentFor(hash).GetEntry(key, hash);
                }

                public bool RemoveEntry(E entry, V value)
                {
                    if (entry == null)
                    {
                        throw new NullReferenceException("entry");
                    }
                    int hash = impl.strategy.GetHash(entry);
                    return impl.SegmentFor(hash).RemoveEntry(entry, hash, value);
                }

                public bool RemoveEntry(E entry)
                {
                    if (entry == null)
                    {
                        throw new NullReferenceException("entry");
                    }
                    int hash = impl.strategy.GetHash(entry);
                    return impl.SegmentFor(hash).RemoveEntry(entry, hash);
                }
            }

            internal Segment[] NewSegmentArray(int ssize)
            {
                // Note: This is the only way I could figure out how to create
                // a segment array (the compile has a tough time with arrays of
                // inner classes of generic types apparently). Safe because we're
                // restricting what can go in the array and no one has an
                // unrestricted reference.
                return (Segment[])Array.CreateInstance(typeof(Segment), ssize);
            }

            /* ---------------- Small Utilities -------------- */

            /// <summary>
            /// 返回具有给定哈希值的被用于key的segment
            /// </summary>
            /// <param name="hash">key的哈希码</param>
            /// <returns></returns>
            internal Segment SegmentFor(int hash)
            {

                return segments[(Hashing.RightMove(hash, segmentShift)) & segmentMask];
            }

            /// <summary>
            /// 一个特殊版本的哈希表。他维护一个实体列表的表格，此实体列表
            /// 总是保持一个持久状态，因此能够不需要锁定而读取。所有列表的
            /// 添加都在每一个bin之前执行，这使得非常容易检查改变，并能够
            /// 非常快速的移动。当节点被改变时，一个新的节点将被创建以替换
            /// 他们。读取操作也能够不具有锁定，但这依赖于选择的volatiles的
            /// 使用以便确定完整的写入操作是否被其他线程执行。对于大部分情况下，
            /// count域--跟踪元素个数的域，作为volatile变量已确保可见，因为
            /// 这个域需要以多种读取方式读取：
            /// - 所有读取操作必须首先读取count域，并且如果此域为0则不应该访问表格实体
            /// - 所有写入操作应该在结构化的改变所有bin后写入count域
            /// </summary>
            public sealed class Segment
            {
                internal volatile int count;

                /// <summary>
                /// 改变表大小的数目。在大量读取方法期间使用以确保他们看到一致的快照：如果
                /// modCounts在一个segment计算大小或检查包含的值期间改变，则我们可能具有
                /// 一个不一致的状态的视图，以便重试
                /// </summary>
                internal int modCount;

                /// <summary>
                /// 当表格的大小超出此阀值时，则表格打下将扩充（此域的值总是为capacity*loadFactor）
                /// </summary>
                internal int threshold;

                /// <summary>
                /// segment维护的表，他是一个原子操作数组，每次操作都将使用Interlocked对象进行
                /// </summary>
                private volatile AtomicReferenceArray<E> table;

                public AtomicReferenceArray<E> Table
                {
                    get { return table; }
                }

                internal Impl<K, V, E> impl;

                internal Segment(int initialCapacity, Impl<K, V, E> impl)
                {
                    this.impl = impl;
                    SetTable(NewEntryArray(initialCapacity));
                }

                AtomicReferenceArray<E> NewEntryArray(int size)
                {
                    return new AtomicReferenceArray<E>(size);
                }

                internal void Lock()
                {
                    Monitor.Enter(this);
                }

                internal void UnLock()
                {
                    Monitor.Exit(this);
                }

                /// <summary>
                /// 设置表格为新的哈希实体数组。仅仅当持有锁定或构造器中调用
                /// </summary>
                /// <param name="newTable"></param>
                internal void SetTable(AtomicReferenceArray<E> newTable)
                {
                    this.threshold = (int)(newTable.Length * this.impl.loadFactor);
                    this.table = newTable;
                }

                /// <summary>
                /// 为给定的哈希值获取bin实体的第一个正确的对象
                /// </summary>
                /// <param name="hash"></param>
                /// <returns></returns>
                internal E GetFirst(int hash)
                {
                    AtomicReferenceArray<E> table = this.table;
                    return table[hash & (table.Length - 1)];
                }

                /* 哈希字典方法的特定实现 */

                public E GetEntry(object key, int hash)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    if (count != 0)
                    { // read-volatile
                        for (E e = GetFirst(hash); e != null; e = s.GetNext(e))
                        {
                            if (s.GetHash(e) != hash)
                            {
                                continue;
                            }

                            K entryKey = s.GetKey(e);
                            if (entryKey == null)
                            {
                                continue;
                            }

                            if (s.EqualKeys(entryKey, key))
                            {
                                return e;
                            }
                        }
                    }

                    return null;
                }

                internal V Get(object key, int hash)
                {
                    E entry = GetEntry(key, hash);
                    if (entry == null)
                    {
                        return default(V);
                    }
                    return this.impl.strategy.GetValue(entry);
                }

                internal bool ContainsKey(object key, int hash)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    if (count != 0)
                    { // read-volatile
                        for (E e = GetFirst(hash); e != null; e = s.GetNext(e))
                        {
                            if (s.GetHash(e) != hash)
                            {
                                continue;
                            }

                            K entryKey = s.GetKey(e);
                            if (entryKey == null)
                            {
                                continue;
                            }

                            if (s.EqualKeys(entryKey, key))
                            {
                                // Return true only if this entry has a value.
                                return s.GetValue(e) != null;
                            }
                        }
                    }
                    return false;
                }

                internal bool ContainsValue(object value)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    if (count != 0)
                    { // read-volatile
                        AtomicReferenceArray<E> table = this.table;
                        int length = table.Length;
                        for (int i = 0; i < length; i++)
                        {
                            for (E e = table[i]; e != null; e = s.GetNext(e))
                            {
                                V entryValue = s.GetValue(e);

                                // If the value disappeared, this entry is partially collected,
                                // and we should skip it.
                                if (entryValue == null)
                                {
                                    continue;
                                }

                                if (s.EqualValues(entryValue, value))
                                {
                                    return true;
                                }
                            }
                        }
                    }
                    return false;
                }

                internal bool Replace(K key, int hash, V oldValue, V newValue)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        for (E e = GetFirst(hash); e != null; e = s.GetNext(e))
                        {
                            K entryKey = s.GetKey(e);
                            if (s.GetHash(e) == hash && entryKey != null
                                && s.EqualKeys(key, entryKey))
                            {
                                // If the value disappeared, this entry is partially collected,
                                // and we should pretend like it doesn't exist.
                                V entryValue = s.GetValue(e);
                                if (entryValue == null)
                                {
                                    return false;
                                }

                                if (s.EqualValues(entryValue, oldValue))
                                {
                                    s.SetValue(e, newValue);
                                    return true;
                                }
                            }
                        }

                        return false;
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                internal V Replace(K key, int hash, V newValue)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        for (E e = GetFirst(hash); e != null; e = s.GetNext(e))
                        {
                            K entryKey = s.GetKey(e);
                            if (s.GetHash(e) == hash && entryKey != null
                                && s.EqualKeys(key, entryKey))
                            {
                                // If the value disappeared, this entry is partially collected,
                                // and we should pretend like it doesn't exist.
                                V entryValue = s.GetValue(e);
                                if (entryValue == null)
                                {
                                    return default(V);
                                }

                                s.SetValue(e, newValue);
                                return entryValue;
                            }
                        }

                        return default(V);
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                internal V Put(K key, int hash, V value, bool onlyIfAbsent)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        int count = this.count;
                        if (count++ > this.threshold)
                        { // ensure capacity
                            Expand();
                        }

                        AtomicReferenceArray<E> table = this.table;
                        int index = hash & (table.Length - 1);

                        E first = table[index];

                        // Look for an existing entry.
                        for (E e = first; e != null; e = s.GetNext(e))
                        {
                            K entryKey = s.GetKey(e);
                            if (s.GetHash(e) == hash && entryKey != null
                                && s.EqualKeys(key, entryKey))
                            {
                                // We found an existing entry.

                                // If the value disappeared, this entry is partially collected,
                                // and we should pretend like it doesn't exist.
                                V entryValue = s.GetValue(e);
                                if (onlyIfAbsent && entryValue != null)
                                {
                                    return entryValue;
                                }

                                s.SetValue(e, value);
                                return entryValue;
                            }
                        }

                        // Create a new entry.
                        ++modCount;
                        E newEntry = s.NewEntry(key, hash, first);
                        s.SetValue(newEntry, value);
                        table[index] = newEntry;
                        this.count = count; // write-volatile
                        return default(V);
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                /// <summary>
                /// 如果可能则扩充表格
                /// </summary>
                internal void Expand()
                {
                    AtomicReferenceArray<E> oldTable = table;
                    int oldCapacity = oldTable.Length;
                    if (oldCapacity >= MAXIMUM_CAPACITY)
                    {
                        return;
                    }

                    Strategy<K, V, E> s = this.impl.strategy;
                    AtomicReferenceArray<E> newTable = NewEntryArray(oldCapacity << 1);
                    threshold = (int)(newTable.Length * this.impl.loadFactor);
                    int newMask = newTable.Length - 1;
                    for (int oldIndex = 0; oldIndex < oldCapacity; oldIndex++)
                    {
                        // We need to guarantee that any existing reads of old Map can
                        //  proceed. So we cannot yet null out each bin.
                        E head = oldTable[oldIndex];

                        if (head != null)
                        {
                            E next = s.GetNext(head);
                            int headIndex = s.GetHash(head) & newMask;

                            // Single node on list
                            if (next == null)
                            {
                                newTable[headIndex] = head;
                            }
                            else
                            {
                                // Reuse the consecutive sequence of nodes with the same target
                                // index from the end of the list. tail points to the first
                                // entry in the reusable list.
                                E tail = head;
                                int tailIndex = headIndex;
                                for (E last = next; last != null; last = s.GetNext(last))
                                {
                                    int newIndex = s.GetHash(last) & newMask;
                                    if (newIndex != tailIndex)
                                    {
                                        // The index changed. We'll need to copy the previous entry.
                                        tailIndex = newIndex;
                                        tail = last;
                                    }
                                }
                                newTable[tailIndex] = tail;

                                // Clone nodes leading up to the tail.
                                for (E e = head; e != tail; e = s.GetNext(e))
                                {
                                    K key = s.GetKey(e);
                                    if (key != null)
                                    {
                                        int newIndex = s.GetHash(e) & newMask;
                                        E newNext = newTable[newIndex];
                                        newTable[newIndex] = s.CopyEntry(key, e, newNext);
                                    }
                                    else
                                    {
                                        // Key was reclaimed. Skip entry.
                                    }
                                }
                            }
                        }
                    }
                    table = newTable;
                }

                internal V Remove(object key, int hash)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        int count = this.count - 1;
                        AtomicReferenceArray<E> table = this.table;
                        int index = hash & (table.Length - 1);
                        E first = table[index];

                        for (E e = first; e != null; e = s.GetNext(e))
                        {
                            K entryKey = s.GetKey(e);
                            if (s.GetHash(e) == hash && entryKey != null
                                && s.EqualKeys(entryKey, key))
                            {
                                V entryValue = this.impl.strategy.GetValue(e);
                                // All entries following removed node can stay
                                // in list, but all preceding ones need to be
                                // cloned.
                                ++modCount;
                                E newFirst = s.GetNext(e);
                                for (E p = first; p != e; p = s.GetNext(p))
                                {
                                    K pKey = s.GetKey(p);
                                    if (pKey != null)
                                    {
                                        newFirst = s.CopyEntry(pKey, p, newFirst);
                                    }
                                    else
                                    {
                                        // Key was reclaimed. Skip entry.
                                    }
                                }
                                table[index] = newFirst;
                                this.count = count; // write-volatile
                                return entryValue;
                            }
                        }

                        return default(V);
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                internal bool Remove(object key, int hash, object value)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        int count = this.count - 1;
                        AtomicReferenceArray<E> table = this.table;
                        int index = hash & (table.Length - 1);
                        E first = table[index];

                        for (E e = first; e != null; e = s.GetNext(e))
                        {
                            K entryKey = s.GetKey(e);
                            if (s.GetHash(e) == hash && entryKey != null
                                && s.EqualKeys(entryKey, key))
                            {
                                V entryValue = this.impl.strategy.GetValue(e);
                                if (entryValue.Equals(value) 
                                    || (value != null && !entryValue.Equals(default(V))
                                    && s.EqualValues(entryValue, value)))
                                {
                                    // All entries following removed node can stay
                                    // in list, but all preceding ones need to be
                                    // cloned.
                                    ++modCount;
                                    E newFirst = s.GetNext(e);
                                    for (E p = first; p != e; p = s.GetNext(p))
                                    {
                                        K pKey = s.GetKey(p);
                                        if (pKey != null)
                                        {
                                            newFirst = s.CopyEntry(pKey, p, newFirst);
                                        }
                                        else
                                        {
                                            // Key was reclaimed. Skip entry.
                                        }
                                    }
                                    table[index] = newFirst;
                                    this.count = count; // write-volatile
                                    return true;
                                }
                                else
                                {
                                    return false;
                                }
                            }
                        }

                        return false;
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                public bool RemoveEntry(E entry, int hash, V value)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        int count = this.count - 1;
                        AtomicReferenceArray<E> table = this.table;
                        int index = hash & (table.Length - 1);
                        E first = table[index];

                        for (E e = first; e != null; e = s.GetNext(e))
                        {
                            if (s.GetHash(e) == hash && entry.Equals(e))
                            {
                                V entryValue = s.GetValue(e);
                                if (entryValue.Equals(value) || (value != null
                                    && s.EqualValues(entryValue, value)))
                                {
                                    // All entries following removed node can stay
                                    // in list, but all preceding ones need to be
                                    // cloned.
                                    ++modCount;
                                    E newFirst = s.GetNext(e);
                                    for (E p = first; p != e; p = s.GetNext(p))
                                    {
                                        K pKey = s.GetKey(p);
                                        if (pKey != null)
                                        {
                                            newFirst = s.CopyEntry(pKey, p, newFirst);
                                        }
                                        else
                                        {
                                            // Key was reclaimed. Skip entry.
                                        }
                                    }
                                    table[index] = newFirst;
                                    this.count = count; // write-volatile
                                    return true;
                                }
                                else
                                {
                                    return false;
                                }
                            }
                        }

                        return false;
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                public bool RemoveEntry(E entry, int hash)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    Monitor.Enter(this);
                    try
                    {
                        int count = this.count - 1;
                        AtomicReferenceArray<E> table = this.table;
                        int index = hash & (table.Length - 1);
                        E first = table[index];

                        for (E e = first; e != null; e = s.GetNext(e))
                        {
                            if (s.GetHash(e) == hash && entry.Equals(e))
                            {
                                // All entries following removed node can stay
                                // in list, but all preceding ones need to be
                                // cloned.
                                ++modCount;
                                E newFirst = s.GetNext(e);
                                for (E p = first; p != e; p = s.GetNext(p))
                                {
                                    K pKey = s.GetKey(p);
                                    if (pKey != null)
                                    {
                                        newFirst = s.CopyEntry(pKey, p, newFirst);
                                    }
                                    else
                                    {
                                        // Key was reclaimed. Skip entry.
                                    }
                                }
                                table[index] = newFirst;
                                this.count = count; // write-volatile
                                return true;
                            }
                        }

                        return false;
                    }
                    finally
                    {
                        Monitor.Exit(this);
                    }
                }

                public void Clear()
                {
                    if (count != 0)
                    {
                        Monitor.Enter(this);
                        try
                        {
                            AtomicReferenceArray<E> table = this.table;
                            for (int i = 0; i < table.Length; i++)
                            {
                                table[i] = null;
                            }
                            ++modCount;
                            count = 0; // write-volatile
                        }
                        finally
                        {
                            Monitor.Exit(this);
                        }
                    }
                }
            }

            /* ---------------- Public operations -------------- */
            public bool IsEmpty
            {
                get
                {
                    Segment[] segments = this.segments;
                    /*
                     * We keep track of per-segment modCounts to avoid ABA
                     * problems in which an element in one segment was added and
                     * in another removed during traversal, in which case the
                     * table was never actually empty at any point. Note the
                     * similar use of modCounts in the size() and containsValue()
                     * methods, which are the only other methods also susceptible
                     * to ABA problems.
                     */
                    int[] mc = new int[segments.Length];
                    int mcsum = 0;
                    for (int i = 0; i < segments.Length; ++i)
                    {
                        if (segments[i].count != 0)
                        {
                            return false;
                        }
                        else
                        {
                            mcsum += mc[i] = segments[i].modCount;
                        }
                    }
                    // If mcsum happens to be zero, then we know we got a snapshot
                    // before any modifications at all were made.  This is
                    // probably common enough to bother tracking.
                    if (mcsum != 0)
                    {
                        for (int i = 0; i < segments.Length; ++i)
                        {
                            if (segments[i].count != 0 ||
                                mc[i] != segments[i].modCount)
                            {
                                return false;
                            }
                        }
                    }
                    return true;
                }
            }

            public int Count
            {
                get
                {
                    Segment[] segments = this.segments;
                    long sum = 0;
                    long check = 0;
                    int[] mc = new int[segments.Length];
                    // Try a few times to get accurate count. On failure due to
                    // continuous async changes in table, resort to locking.
                    for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k)
                    {
                        check = 0;
                        sum = 0;
                        int mcsum = 0;
                        for (int i = 0; i < segments.Length; ++i)
                        {
                            sum += segments[i].count;
                            mcsum += mc[i] = segments[i].modCount;
                        }
                        if (mcsum != 0)
                        {
                            for (int i = 0; i < segments.Length; ++i)
                            {
                                check += segments[i].count;
                                if (mc[i] != segments[i].modCount)
                                {
                                    check = -1; // force retry
                                    break;
                                }
                            }
                        }
                        if (check == sum)
                        {
                            break;
                        }
                    }
                    if (check != sum)
                    { // Resort to locking all segments
                        sum = 0;
                        foreach (Segment segment in segments)
                        {
                            segment.Lock();
                        }
                        foreach (Segment segment in segments)
                        {
                            sum += segment.count;
                        }
                        foreach (Segment segment in segments)
                        {
                            segment.UnLock();
                        }
                    }
                    if (sum > int.MaxValue)
                    {
                        return int.MaxValue;
                    }
                    else
                    {
                        return (int)sum;
                    }
                }
            }

            public virtual V this[K key]
            {
                 get
                {
                    if (key == null)
                    {
                        throw new ArgumentNullException("key");
                    }
                    if (!ContainsKey(key))
                    {
                        throw new KeyNotFoundException(key + " not found");
                    }
                    int hash = Hash(key);
                    return SegmentFor(hash).Get(key, hash);
                }
                set
                {
                    if (key == null)
                    {
                        throw new ArgumentNullException("key");
                    }
                    if (value == null)
                    {
                        throw new ArgumentNullException("value");
                    }
                    if (!ContainsKey(key))
                    {
                        throw new KeyNotFoundException(key + " not found");
                    }
                    int hash = Hash(key);
                    SegmentFor(hash).Put(key, hash, value, false);
                }
            }

            public virtual bool ContainsKey(K key)
            {
                if (key == null)
                {
                    throw new ArgumentNullException("key");
                }
                int hash = Hash(key);
                return SegmentFor(hash).ContainsKey(key, hash);
            }

            public virtual void Add(K key, V value)
            {
                if (key == null)
                {
                    throw new ArgumentNullException("key");
                }
                if (value == null)
                {
                    throw new ArgumentNullException("value");
                }
                int hash = Hash(key);
                SegmentFor(hash).Put(key, hash, value, false);
            }

            ISet<K> keySet;

            public virtual ICollection<K> Keys
            {
                get
                {
                    ISet<K> ks = keySet;
                    return (ks != null) ? ks : (keySet = new KeySet(this));
                }
            }

            public virtual bool Remove(K key)
            {
                if (key == null)
                {
                    throw new ArgumentNullException("key");
                }
                int hash = Hash(key);
                return SegmentFor(hash).Remove(key, hash) != null ? true : false;
            }

            public virtual bool TryGetValue(K key, out V value)
            {
                if (ContainsKey(key))
                {
                    value = this[key];
                    return true;
                }
                else
                {
                    value = default(V);
                    return false;
                }
            }

            ICollection<V> values;

            public virtual ICollection<V> Values
            {
                get
                {
                    ICollection<V> vs = values;
                    return (vs != null) ? vs : (values = new EntryValues(this));
                }
            }

            public virtual void Add(KeyValuePair<K, V> item)
            {
                Add(item.Key, item.Value);
            }

            public virtual void Clear()
            {
                foreach (Segment segment in segments)
                {
                    segment.Clear();
                }
            }

            public virtual bool Contains(KeyValuePair<K, V> item)
            {
                if (item.Value == null)
                {
                    throw new NullReferenceException("value");
                }

                // See explanation of modCount use above

                Segment[] segments = this.segments;
                int[] mc = new int[segments.Length];

                // Try a few times without locking
                for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k)
                {
                    int mcsum = 0;
                    for (int i = 0; i < segments.Length; ++i)
                    {
                        int c = segments[i].count;
                        mcsum += mc[i] = segments[i].modCount;
                        if (segments[i].ContainsValue(item.Value))
                        {
                            return true;
                        }
                    }
                    bool cleanSweep = true;
                    if (mcsum != 0)
                    {
                        for (int i = 0; i < segments.Length; ++i)
                        {
                            int c = segments[i].count;
                            if (mc[i] != segments[i].modCount)
                            {
                                cleanSweep = false;
                                break;
                            }
                        }
                    }
                    if (cleanSweep)
                    {
                        return false;
                    }
                }
                // Resort to locking all segments
                foreach (Segment segment in segments)
                {
                    segment.Lock();
                }
                bool found = false;
                try
                {
                    foreach (Segment segment in segments)
                    {
                        if (segment.ContainsValue(item.Value))
                        {
                            found = true;
                            break;
                        }
                    }
                }
                finally
                {
                    foreach (Segment segment in segments)
                    {
                        segment.UnLock();
                    }
                }
                return found;
            }

            public virtual void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)
            {
                GetEnumerator();
                ((EntrySet)entrySet).CopyTo(array, arrayIndex);
            }

            public virtual bool IsReadOnly
            {
                get { return false; }
            }

            public virtual bool Remove(KeyValuePair<K, V> item)
            {
                if (item.Key == null)
                {
                    throw new NullReferenceException("key");
                }
                int hash = Hash(item.Key);
                return SegmentFor(hash).Remove(item.Key, hash, item.Value);
            }

            ISet<KeyValuePair<K, V>> entrySet;

            public virtual IEnumerator<KeyValuePair<K, V>> GetEnumerator()
            {
                ISet<KeyValuePair<K, V>> es = entrySet;
                return (es != null) ? es.GetEnumerator() : (entrySet = new EntrySet(this)).GetEnumerator();
            }

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }

            public virtual V PutIfAbsent(K key, V value)
            {
                if (key == null)
                {
                    throw new NullReferenceException("key");
                }
                if (value == null)
                {
                    throw new NullReferenceException("value");
                }
                int hash = Hash(key);
                return SegmentFor(hash).Put(key, hash, value, true);
            }

            public virtual bool Remove(K key, V value)
            {
                return Remove(new KeyValuePair<K, V>(key, value));
            }

            public virtual bool Replace(K key, V oldValue, V newValue)
            {
                if (key == null)
                {
                    throw new ArgumentNullException("key");
                }
                if (oldValue == null)
                {
                    throw new ArgumentNullException("oldValue");
                }
                if (newValue == null)
                {
                    throw new ArgumentNullException("newValue");
                }
                int hash = Hash(key);
                return SegmentFor(hash).Replace(key, hash, oldValue, newValue);
            }

            public virtual V Replace(K key, V value)
            {
                if (key == null)
                {
                    throw new ArgumentNullException("key");
                }
                if (value == null)
                {
                    throw new ArgumentNullException("value");
                }
                int hash = Hash(key);
                return SegmentFor(hash).Replace(key, hash, value);
            }

            /* ---------------- Iterator Support -------------- */

            internal abstract class HashIterator
            {

                int nextSegmentIndex;
                int nextTableIndex;
                AtomicReferenceArray<E> currentTable;
                E nextEntry;
                WriteThroughEntry nextExternal;
                WriteThroughEntry lastReturned;
                Impl<K, V, E> impl;

                internal HashIterator(Impl<K, V, E> impl)
                {
                    this.impl = impl;
                    nextSegmentIndex = this.impl.segments.Length - 1;
                    nextTableIndex = -1;
                    Advance();
                }

                public bool HasMoreElements()
                {
                    return HasNext();
                }

                internal void Advance()
                {
                    nextExternal = default(WriteThroughEntry);

                    if (NextInChain())
                    {
                        return;
                    }

                    if (NextInTable())
                    {
                        return;
                    }

                    while (nextSegmentIndex >= 0)
                    {
                        Segment seg = this.impl.segments[nextSegmentIndex--];
                        if (seg.count != 0)
                        {
                            currentTable = seg.Table;
                            nextTableIndex = currentTable.Length - 1;
                            if (NextInTable())
                            {
                                return;
                            }
                        }
                    }
                }

                /**
                 * Finds the next entry in the current chain. Returns true if an entry
                 * was found.
                 */
                internal bool NextInChain()
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    if (nextEntry != null)
                    {
                        for (nextEntry = s.GetNext(nextEntry); nextEntry != null;
                            nextEntry = s.GetNext(nextEntry))
                        {
                            if (AdvanceTo(nextEntry))
                            {
                                return true;
                            }
                        }
                    }
                    return false;
                }

                /**
                 * Finds the next entry in the current table. Returns true if an entry
                 * was found.
                 */
                internal bool NextInTable()
                {
                    while (nextTableIndex >= 0)
                    {
                        if ((nextEntry = currentTable[nextTableIndex--]) != null)
                        {
                            if (AdvanceTo(nextEntry) || NextInChain())
                            {
                                return true;
                            }
                        }
                    }
                    return false;
                }

                /**
                 * Advances to the given entry. Returns true if the entry was valid,
                 * false if it should be skipped.
                 */
                internal bool AdvanceTo(E entry)
                {
                    Strategy<K, V, E> s = this.impl.strategy;
                    K key = s.GetKey(entry);
                    V value = s.GetValue(entry);
                    if (key != null && value != null)
                    {
                        nextExternal = new WriteThroughEntry(this.impl, key, value);
                        return true;
                    }
                    else
                    {
                        // Skip partially reclaimed entry.
                        return false;
                    }
                }

                public bool HasNext()
                {
                    return nextExternal != null;
                }

                internal WriteThroughEntry NextEntry()
                {
                    if (nextExternal == null)
                    {
                        throw new NullReferenceException();
                    }
                    lastReturned = nextExternal;
                    Advance();
                    return lastReturned;
                }

                public void Remove()
                {
                    if (lastReturned == null)
                    {
                        throw new ArgumentNullException();
                    }
                    this.impl.Remove(lastReturned.Key);
                    lastReturned = default(WriteThroughEntry);
                }
            }

            internal sealed class KeyIterator : HashIterator, IEnumerator<K>
            {

                public KeyIterator(Impl<K, V, E> impl) : base(impl) { }

                private K current;

                public K Current
                {
                    get { return current; }
                }

                public void Dispose()
                {
                    current = default(K);
                }

                object System.Collections.IEnumerator.Current
                {
                    get { return Current; }
                }

                public bool MoveNext()
                {
                    try
                    {
                        WriteThroughEntry entry = base.NextEntry();
                        current = entry.Key;
                        return true;
                    }
                    catch (NullReferenceException e)
                    {
                        return false;
                    }
                }

                public void Reset()
                {
                    throw new NotSupportedException();
                }
            }

            internal sealed class ValueIterator : HashIterator, IEnumerator<V>
            {

                public ValueIterator(Impl<K, V, E> impl) : base(impl) { }
                private V current;

                public V Current
                {
                    get { return current; }
                }

                public void Dispose()
                {
                    current = default(V);
                }

                object System.Collections.IEnumerator.Current
                {
                    get { return Current; }
                }

                public bool MoveNext()
                {
                    try
                    {
                        WriteThroughEntry entry = base.NextEntry();
                        current = entry.Value;
                        return true;
                    }
                    catch (NullReferenceException e)
                    {
                        return false;
                    }
                }

                public void Reset()
                {
                    throw new NotSupportedException();
                }
            }

            /**
             * Custom Entry class used by EntryIterator.next(), that relays setValue
             * changes to the underlying map.
             */
            public class WriteThroughEntry
            {
                readonly K key;

                public virtual K Key
                {
                    get { return key; }
                }

                V value;

                public virtual V Value
                {
                    get { return this.value; }
                }

                private Impl<K, V, E> impl;


                public WriteThroughEntry(Impl<K, V, E> impl, K key, V value)
                {
                    this.key = key;
                    this.value = value;
                    this.impl = impl;
                }

                /**
                 * Set our entry's value and write through to the map. The value to
                 * return is somewhat arbitrary here. Since a WriteThroughEntry does not
                 * necessarily track asynchronous changes, the most recent "previous"
                 * value could be different from what we return (or could even have been
                 * removed in which case the put will re-establish). We do not and
                 * cannot guarantee more.
                 */
                public virtual V SetValue(V value)
                {
                    if (value == null)
                    {
                        throw new NullReferenceException();
                    }
                    V oldValue = this.impl.ContainsKey(key) == true ? this.impl[key] : default(V);
                    this.impl.Add(Key, value);
                    this.value = value;
                    return oldValue;
                }
            }


            internal sealed class EntryIterator : HashIterator, IEnumerator<KeyValuePair<K, V>>
            {
                public EntryIterator(Impl<K, V, E> impl) : base(impl) { }
                private KeyValuePair<K, V> current;

                public KeyValuePair<K, V> Current
                {
                    get { return current; }
                }

                public void Dispose()
                {
                    current = default(KeyValuePair<K, V>);
                }

                object System.Collections.IEnumerator.Current
                {
                    get { return Current; }
                }

                public bool MoveNext()
                {
                    try
                    {
                        WriteThroughEntry entry = NextEntry();
                        current = new KeyValuePair<K, V>(entry.Key, entry.Value);
                        return true;
                    }
                    catch (NullReferenceException e)
                    {
                        return false;
                    }
                }

                public void Reset()
                {
                    throw new NotSupportedException();
                }
            }

            public sealed class KeySet : ISet<K>
            {

                private Impl<K, V, E> impl;

                public KeySet(Impl<K, V, E> impl)
                {
                    this.impl = impl;
                }

                public bool Add(K item)
                {
                    throw new NotSupportedException();
                }

                public void ExceptWith(IEnumerable<K> other)
                {
                    if (other == null)
                        throw new ArgumentNullException();
                    IEnumerator<K> iter = other.GetEnumerator();
                    if (Count > other.ToArray<K>().Length)
                    {
                        while (iter.MoveNext())
                        {
                            Remove(iter.Current);
                        }
                    }
                    else
                    {
                        K[] array = new K[this.Count];
                        this.CopyTo(array, 0);
                        for (int i = 0; i < array.Length; i++)
                        {
                            if (other.Contains(array[i]))
                            {
                                this.Remove(array[i]);
                            }
                        }
                    }
                }

                public void IntersectWith(IEnumerable<K> other)
                {
                    if (other == null)
                        throw new ArgumentNullException();
                    K[] array = new K[this.Count];
                    this.CopyTo(array, 0);
                    for (int i = 0; i < array.Length; i++)
                    {
                        if (!other.Contains(array[i]))
                        {
                            this.Remove(array[i]);
                        }
                    }
                }

                public bool CheckSize(IEnumerable<K> other)
                {
                    if (this.Count == other.Count<K>())
                        return true;
                    return false;
                }

                public bool IsProperSubsetOf(IEnumerable<K> other)
                {
                    foreach (K key in this)
                    {
                        if (!other.Contains<K>(key))
                            return false;
                    }
                    return !CheckSize(other);
                }

                public bool IsProperSupersetOf(IEnumerable<K> other)
                {
                    foreach (K key in other)
                    {
                        if (!this.Contains<K>(key))
                            return false;
                    }
                    return !CheckSize(other);
                }

                public bool IsSubsetOf(IEnumerable<K> other)
                {
                    foreach (K key in this)
                    {
                        if (!other.Contains<K>(key))
                            return false;
                    }
                    return true;
                }

                public bool IsSupersetOf(IEnumerable<K> other)
                {
                    foreach (K key in other)
                    {
                        if (!this.Contains<K>(key))
                            return false;
                    }
                    return true;
                }

                public bool Overlaps(IEnumerable<K> other)
                {
                    foreach (K key in this)
                    {
                        if (other.Contains<K>(key))
                            return true;
                    }
                    return false;
                }

                public bool SetEquals(IEnumerable<K> other)
                {
                    if (CheckSize(other))
                    {
                        return Overlaps(other);
                    }
                    return false;

                }

                public void SymmetricExceptWith(IEnumerable<K> other)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                public void UnionWith(IEnumerable<K> other)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                void ICollection<K>.Add(K item)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                public void Clear()
                {
                    this.impl.Clear();
                }

                public bool Contains(K item)
                {
                    return this.impl.ContainsKey(item);
                }

                public void CopyTo(K[] array, int arrayIndex)
                {
                    K[] source = this.ToArray<K>();
                    Array.Copy(source, 0, array, arrayIndex, array.Length - arrayIndex);
                }

                public int Count
                {
                    get { return this.impl.Count; }
                }

                public bool IsReadOnly
                {
                    get { return false; }
                }

                public bool Remove(K item)
                {
                    return this.impl.Remove(item);
                }

                public IEnumerator<K> GetEnumerator()
                {
                    return new KeyIterator(this.impl);
                }

                System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
                {
                    return GetEnumerator();
                }
            }

            public sealed class EntryValues : ICollection<V>
            {
                private Impl<K, V, E> impl;

                public EntryValues(Impl<K, V, E> impl)
                {
                    this.impl = impl;
                }

                public void Add(V item)
                {//不支持添加元素
                    throw new NotSupportedException(); throw new NotImplementedException();
                }

                public void Clear()
                {
                    this.impl.Clear();
                }

                public bool Contains(V item)
                {
                    return this.impl.Contains(new KeyValuePair<K, V>(default(K), item));
                }

                public void CopyTo(V[] array, int arrayIndex)
                {
                    V[] source = this.ToArray<V>();
                    Array.Copy(source, 0, array, arrayIndex, array.Length - arrayIndex);
                }

                public int Count
                {
                    get { return this.impl.Count; }
                }

                public bool IsReadOnly
                {
                    get { return false; }
                }

                public bool Remove(V item)
                {
                    ICollection<K> keys = this.impl.Keys;
                    foreach (K k in keys)
                    {
                        if (this.impl[k].Equals(item))
                        {
                            this.impl.Remove(k);
                            return true;
                        }
                    }
                    return false;
                }

                public IEnumerator<V> GetEnumerator()
                {
                    return new ValueIterator(this.impl);
                }

                System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
                {
                    return GetEnumerator();
                }
            }

            public sealed class EntrySet : ISet<KeyValuePair<K, V>>
            {

                private Impl<K, V, E> impl;

                public EntrySet(Impl<K, V, E> impl)
                {
                    this.impl = impl;
                }

                public bool Add(KeyValuePair<K, V> item)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                public void ExceptWith(IEnumerable<KeyValuePair<K, V>> other)
                {
                    if (other == null)
                        throw new ArgumentNullException();
                    IEnumerator<KeyValuePair<K, V>> iter = other.GetEnumerator();
                    if (Count > other.ToArray<KeyValuePair<K, V>>().Length)
                    {
                        while (iter.MoveNext())
                        {
                            Remove(iter.Current);
                        }
                    }
                    else
                    {
                        KeyValuePair<K, V>[] array = new KeyValuePair<K, V>[this.Count];
                        this.CopyTo(array, 0);
                        for (int i = 0; i < array.Length; i++)
                        {
                            if (other.Contains(array[i]))
                            {
                                this.Remove(array[i]);
                            }
                        }
                    }
                }

                public void IntersectWith(IEnumerable<KeyValuePair<K, V>> other)
                {
                    if (other == null)
                        throw new ArgumentNullException();
                    KeyValuePair<K, V>[] array = new KeyValuePair<K, V>[this.Count];
                    this.CopyTo(array, 0);
                    for (int i = 0; i < array.Length; i++)
                    {
                        if (!other.Contains(array[i]))
                        {
                            this.Remove(array[i]);
                        }
                    }
                }

                public bool CheckSize(IEnumerable<KeyValuePair<K, V>> other)
                {
                    if (this.Count == other.Count<KeyValuePair<K, V>>())
                        return true;
                    return false;
                }

                public bool IsProperSupersetOf(IEnumerable<KeyValuePair<K, V>> other)
                {
                    foreach (KeyValuePair<K, V> key in other)
                    {
                        if (!this.Contains<KeyValuePair<K, V>>(key))
                            return false;
                    }
                    return !CheckSize(other);
                }

                public bool IsProperSubsetOf(IEnumerable<KeyValuePair<K, V>> other)
                {
                    if (Count == other.Count())
                        return false;
                    return IsSubsetOf(other);
                }

                public bool IsSubsetOf(IEnumerable<KeyValuePair<K, V>> other)
                {
                    foreach (KeyValuePair<K, V> key in this)
                    {
                        if (!other.Contains<KeyValuePair<K, V>>(key))
                            return false;
                    }
                    return true;
                }

                public bool IsSupersetOf(IEnumerable<KeyValuePair<K, V>> other)
                {
                    foreach (KeyValuePair<K, V> key in other)
                    {
                        if (!this.Contains<KeyValuePair<K, V>>(key))
                            return false;
                    }
                    return true;
                }

                public bool Overlaps(IEnumerable<KeyValuePair<K, V>> other)
                {
                    foreach (KeyValuePair<K, V> key in this)
                    {
                        if (other.Contains<KeyValuePair<K, V>>(key))
                            return true;
                    }
                    return false;
                }

                public bool SetEquals(IEnumerable<KeyValuePair<K, V>> other)
                {
                    if (CheckSize(other))
                    {
                        return Overlaps(other);
                    }
                    return false;

                }

                public void SymmetricExceptWith(IEnumerable<KeyValuePair<K, V>> other)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                public void UnionWith(IEnumerable<KeyValuePair<K, V>> other)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                void ICollection<KeyValuePair<K, V>>.Add(KeyValuePair<K, V> item)
                {
                    //不支持添加元素
                    throw new NotSupportedException();
                }

                public void Clear()
                {
                    this.impl.Clear();
                }

                public bool Contains(KeyValuePair<K, V> item)
                {
                    KeyValuePair<K, V> e = (KeyValuePair<K, V>)item;
                    K key = e.Key;
                    if (key == null)
                    {
                        return false;
                    }
                    V v = default(V);
                    this.impl.TryGetValue(key, out v);
                    return v != null && this.impl.strategy.EqualValues(v, e.Value);
                }

                public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)
                {
                    KeyValuePair<K, V>[] source = this.ToArray<KeyValuePair<K, V>>();
                    Array.Copy(source, 0, array, arrayIndex, array.Length - arrayIndex);
                }

                public int Count
                {
                    get { return this.impl.Count; }
                }

                public bool IsReadOnly
                {
                    get { return false; }
                }

                public bool Remove(KeyValuePair<K, V> item)
                {
                    return item.Key != null && this.impl.Remove(item.Key, item.Value);
                }

                public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
                {
                    return new EntryIterator(this.impl);
                }

                System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
                {
                    return GetEnumerator();
                }

            }

            /// <summary>
            /// 序列化：initialCapacity、loadFactor、concurrencyLevel、strategy、key0.key1....、key.tostring、null
            /// </summary>
            /// <param name="info"></param>
            /// <param name="context"></param>
            public void GetObjectData(SerializationInfo info, StreamingContext context)
            {
                info.AddValue("initialCapacity", this.Count);
                info.AddValue("loadFactor", this.loadFactor);
                info.AddValue("concurrencyLevel", segments.Length);
                info.AddValue("strategy", strategy);
                int i = 0;
                foreach (KeyValuePair<K, V> entry in this)
                {
                    info.AddValue("key" + i++, entry.Key);
                    info.AddValue(entry.Key.ToString(), entry.Value);
                }
                info.AddValue("null", null); // terminate entries
            }

            /// <summary>
            /// 在反序列化期间使用的域
            /// </summary>
            internal static class Fields
            {
                internal static readonly FieldInfo loadFactor = FindField("loadFactor");
                internal static readonly FieldInfo segmentShift = FindField("segmentShift");
                internal static readonly FieldInfo segmentMask = FindField("segmentMask");
                internal static readonly FieldInfo segments = FindField("segments");
                internal static readonly FieldInfo strategy = FindField("strategy");

                internal static FieldInfo FindField(string name)
                {
                    FieldInfo field = typeof(Impl<K, V, E>).GetField(name, BindingFlags.Instance | BindingFlags.DeclaredOnly | BindingFlags.GetField);
                    if (field == null)
                        throw new NullReferenceException("the field:" + name + " not exist");
                    return field;
                }
            }
        }

        internal class ComputingImpl<K, V, E> : Impl<K, V, E>
            where E : class
            //where V : class
        {
            readonly ComputingStrategy<K, V, E> computingStrategy;
            readonly Func<K, V> computer;

            /**
             * Creates a new, empty map with the specified strategy, initial capacity,
             * load factor and concurrency level.
             */
            public ComputingImpl(ComputingStrategy<K, V, E> strategy, Builder builder, Func<K, V> computer)
                : base(strategy, builder)
            {
                this.computingStrategy = strategy;
                this.computer = computer;
            }

            public override V this[K k]
            {
                get
                {
                    /*
                     * This cast isn't safe, but we can rely on the fact that K is almost
                     * always passed to Map.get(), and tools like IDEs and Findbugs can
                     * catch situations where this isn't the case.
                     *
                     * The alternative is to add an overloaded method, but the chances of
                     * a user calling get() instead of the new API and the risks inherent
                     * in adding a new API outweigh this little hole.
                     */
                    K key = (K)k;

                    if (key == null)
                    {
                        throw new NullReferenceException("key");
                    }

                    int hash = Hash(key);
                    Segment segment = SegmentFor(hash);
                outer: while (true)
                    {
                        E entry = segment.GetEntry(key, hash);
                        if (entry == null)
                        {
                            bool created = false;
                            segment.Lock();
                            try
                            {
                                // Try again--an entry could have materialized in the interim.
                                entry = segment.GetEntry(key, hash);
                                if (entry == null)
                                {
                                    // Create a new entry.
                                    created = true;
                                    int count = segment.count;
                                    if (count++ > segment.threshold)
                                    { // ensure capacity
                                        segment.Expand();
                                    }
                                    AtomicReferenceArray<E> table = segment.Table;
                                    int index = hash & (table.Length - 1);
                                    E first = table[index];
                                    ++segment.modCount;
                                    entry = computingStrategy.NewEntry(key, hash, first);
                                    table[index] = entry;
                                    segment.count = count; // write-volatile
                                }
                            }
                            finally
                            {
                                segment.UnLock();
                            }

                            if (created)
                            {
                                // This thread solely created the entry.
                                bool success = false;
                                try
                                {
                                    V value = computingStrategy.Compute(key, entry, computer);
                                    if (value == null)
                                    {
                                        throw new NullReferenceException("compute() returned null unexpectedly");
                                    }
                                    success = true;
                                    return value;
                                }
                                finally
                                {
                                    if (!success)
                                    {
                                        segment.RemoveEntry(entry, hash);
                                    }
                                }
                            }
                        }

                        // The entry already exists. Wait for the computation.
                        bool interrupted = false;
                        try
                        {
                            while (true)
                            {
                                try
                                {
                                    V value = computingStrategy.WaitForValue(entry);
                                    if (value == null)
                                    {
                                        // Purge entry and try again.
                                        segment.RemoveEntry(entry, hash);
                                        goto outer;
                                    }
                                    return value;
                                }
                                catch (ThreadInterruptedException e)
                                {
                                    interrupted = true;
                                }
                            }
                        }
                        finally
                        {
                            if (interrupted)
                            {
                                Thread.CurrentThread.Interrupt();
                            }
                        }
                    }
                }

            }
        }

        /// <summary>
        /// 一个基本的，使用<code>SimpleInternalEntry</code>的昂贵的策略接口实现。
        /// 他期望被子类化，以便提供自定义的行为。例如，以下的代码创建一个使用byte
        /// 数组作为key的字典：
        /// <example>
        /// return new CustomConcurrentDictionary.Builder().BuildMap(
        ///     new SimpleStrategy<byte[], V>() {
        ///         public int HashKey(object key) {
        ///             return Array.HashCode((byte[]) key);
        ///         }
        ///         public bool EqualKeys(byte[] a, Object b) {
        ///             return Array.Equals(a, (byte[]) b);
        ///         }
        ///     });
        /// }
        /// </example>
        /// </summary>
        /// <typeparam name="K"></typeparam>
        /// <typeparam name="V"></typeparam>
        internal class SimpleStrategy<K, V> : Strategy<K, V, SimpleInternalEntry<K, V>>
        {

            public SimpleInternalEntry<K, V> NewEntry(K key, int hash, SimpleInternalEntry<K, V> next)
            {
                return new SimpleInternalEntry<K, V>(key, hash, default(V), next);
            }

            public SimpleInternalEntry<K, V> CopyEntry(K key, SimpleInternalEntry<K, V> original, SimpleInternalEntry<K, V> newNext)
            {
                return new SimpleInternalEntry<K, V>(key, original.hash, original.value, newNext);
            }

            V Strategy<K, V, SimpleInternalEntry<K, V>>.GetValue(SimpleInternalEntry<K, V> entry)
            {
                return entry.value;
            }

            public void SetValue(SimpleInternalEntry<K, V> entry, V value)
            {
                entry.value = value;
            }

            public bool EqualKeys(K a, object b)
            {
                return a.Equals(b);
            }

            public bool EqualValues(V a, object b)
            {
                return a.Equals(b);
            }

            public int HashKey(object key)
            {
                return key.GetHashCode();
            }

            public K GetKey(SimpleInternalEntry<K, V> entry)
            {
                return entry.key;
            }

            public SimpleInternalEntry<K, V> GetNext(SimpleInternalEntry<K, V> entry)
            {
                return entry.next;
            }

            public int GetHash(SimpleInternalEntry<K, V> entry)
            {
                return entry.hash;
            }

            public void SetInternals(Internals<K, V, SimpleInternalEntry<K, V>> internals)
            {
                // ignore?
            }

        }

        internal class SimpleInternalEntry<K, V>
        {
            internal readonly K key;
            internal readonly int hash;
            internal readonly SimpleInternalEntry<K, V> next;
            internal V value;
            internal SimpleInternalEntry(K key, int hash, V value, SimpleInternalEntry<K, V> next)
            {
                this.key = key;
                this.hash = hash;
                this.value = value;
                this.next = next;
            }
        }
    }

    public class ConcurrentHashDictionary<K, V> : ConcurrentDictionary<K, V>, ConcurrentMap<K, V>
    {
        public ConcurrentHashDictionary(int concurrencyLevel, int capacity) : base(concurrencyLevel, capacity) { }

        public V PutIfAbsent(K key, V value)
        {
            return base.AddOrUpdate(key, value, (k, v) =>
            {
                return v;
            });
        }

        public bool Remove(K key, V value)
        {
            return base.TryRemove(key, out value);
        }

        public bool Replace(K key, V oldValue, V newValue)
        {
            return base.TryUpdate(key, newValue, oldValue);
        }

        public V Replace(K key, V value)
        {
            if (base.ContainsKey(key))
            {
                V old = base[key];
                base[key] = value;
                return old;
            }
            return default(V);
        }
    }
}
